/* ----------
 * pg_lzcompress.c -
 *
 *		这是PostgreSQL的LZ压缩实现。
 *		它使用一个简单的历史表生成2-3字节标签，
 *		能够倒回复制信息3-273字节，最大偏移量为4095。
 *
 *		入口例程：
 *
 *			int32
 *			pglz_compress(const char *source, int32 slen, char *dest,
 *						  const PGLZ_Strategy *strategy);
 *
 *				source是待压缩的输入数据。
 *
 *				slen是输入数据的长度。
 *
 *				dest是压缩结果的输出区域。
 *					它必须至少与PGLZ_MAX_OUTPUT(slen)一样大。
 *
 *				strategy是指向一些控制压缩算法的信息的指针。如果为NULL，则使用编译时默认策略。
 *
 *				返回值是写入缓冲区dest的字节数，或-1如果压缩失败；在后者情况下，dest的内容是未定义的。
 *
 *			int32
 *			pglz_decompress(const char *source, int32 slen, char *dest,
 *							int32 rawsize, bool check_complete)
 *
 *				source是压缩输入。
 *
 *				slen是压缩输入的长度。
 *
 *				dest是将写入未压缩数据的区域。提供足够空间是调用者的责任。
 *
 *					数据按原样写入buff，没有添加终止零字节。
 *
 *				rawsize是未压缩数据的长度。
 *
 *				check_complete是一个标志，用于告知我们是否应在未到达源或dest缓冲区的末尾时返回-1。若调用者仅请求部分结果，则应为false，否则应为true。
 *
 *				返回值是写入缓冲区dest的字节数，或-1如果解压失败。
 *
 *		解压算法和内部数据格式：
 *
 *			它与压缩过的数据本身一起构建。
 *
 *			数据表示法通过描述解压过程来解释最简单。
 *
 *			如果compressed_size == rawsize，则数据以原始字节形式存储。解压缩者简单地将rawsize字节复制到目标位置。
 *
 *			否则，第一个字节告诉接下来的8次该做什么。我们称之为控制字节。
 *
 *			控制字节中的未设置位意味着，接下来有一个未压缩的字节，从输入复制到输出。
 *
 *			控制字节中的设置位意味着，接下来有2-3个字节的标签。标签包含从输出缓冲区中已存在的某些字节复制到当前输出位置的信息。我们称这三个标签字节为T1、T2和T3。复制数据的位置编码为实际输出位置的偏移量。
 *
 *			偏移量在T1的高半字节和T2中。
 *			长度在T1的低半字节中。
 *
 *			因此，2字节标签的16位编码如下：
 *
 *				7---T1--0  7---T2--0
 *				OOOO LLLL  OOOO OOOO
 *
 *			这将偏移量限制为1-4095（12位）和长度限制为3-18（4位），因为3始终会加到其中。生成一个长度为2的2字节标签只节省一个控制位。但我们在标签的可能长度中损失了一个字节。
 *
 *			在实际实现中，2字节标签的长度限制为3-17，因为长度字节中的0xF值具有特殊含义。它意味着下一个后续字节（T3）必须加到长度值18中。这使得偏移量的总体限制为1-4095，长度的限制为3-273。
 *
 *			现在我们成功地解码了一个标签。我们简单地将输出复制到指定长度的当前输出位置，位置为<offset>字节回溯。因此，一系列200个空格（考虑bpchar字段）可以用4字节编码。一个字面空格和一个三字节标签用于以-1偏移复制199个字节。哇 - 这是98%的压缩率！好吧，实现还需要保存原始数据大小，因此我们还需要另外4字节，最后的压缩率为96%，这仍然值得称道。
 *
 *		压缩算法
 *
 *			以下使用的是默认策略中使用的数字。
 *
 *			压缩器对大小在1K到1M之间的属性效果最好。对于较小的项目，字符序列中的冗余可能性不是很大（除非是像尾随空白这样的重复字节的大块区域），而对于较大的项目，我们的4K最大回溯距离又太小。
 *
 *			压缩器创建一个用于位置列表的表。对于每个输入位置（除了最后3个），从4个下一个输入字节构建哈希键，并在适当的列表中记住该位置。因此，表指向可能至少在前4个字符中的匹配字符串的链表。这个操作是在输入被压缩到输出区域的同时进行的。只保留最后4096个输入位置的表项，因为我们无论如何不能使用更大的回指。
 *
 *			哈希表的大小是根据输入大小选择的 - 较大的表有更大的启动成本，因为它需要初始化为零，但减少了长输入上的哈希冲突。
 *
 *			对于输入中的每个字节，使用其哈希键（从该字节和接下来的3个字节构建）来查找表中的相应列表。这些列表记录所有过去具有相同哈希键的字节的位置，按递增的向后偏移顺序排列。现在，对于所用列表中的所有条目，通过比较条目位置的字符与实际输入位置的字符来计算匹配长度。
 *
 *			压缩器从所谓的“good_match”值128开始。它是一个“偏向速度而非压缩率”的优化器。因此，如果查看的第一个条目已经有128个或更多匹配字符，查找将停止，并且该位置将用于输出中的下一个标签。
 *
 *			对于历史列表中的每个后续条目，“good_match”降低10%。因此出现在历史中，需要回溯得越多，压缩器对较短匹配的偏好就越高。这是算法的另一个“速度对比率”的偏好特征。
 *
 *			因此，有3个停止条件来查找匹配：
 *
 *				- 找到匹配 >= good_match
 *				- 没有更多的历史条目可以查看
 *				- 下一个历史条目已经回溯得太远，以至于无法编码到标签中。
 *
 *			最后，匹配算法检查是否找到至少3个或更多字节的匹配，因为这是编码到标签中的最小复制信息量。如果是，则省略标签，扫描所有被覆盖的输入字节以添加历史信息；否则省略一个字面字符，仅添加他的历史条目。
 *
 *		致谢：
 *
 *			非常感谢Adisak Pochanayon，他关于SLZ的文章激励我以这种方式编写PostgreSQL压缩。
 *
 *			Jan Wieck
 *
 * Copyright (c) 1999-2022, PostgreSQL Global Development Group
 *
 * src/common/pg_lzcompress.c
 * ----------
 */
#ifndef FRONTEND
#include "postgres.h"
#else
#include "postgres_fe.h"
#endif

#include <limits.h>

#include "common/pg_lzcompress.h"


/* ----------
 * 本地定义
 * ----------
 */
#define PGLZ_MAX_HISTORY_LISTS	8192	/* 必须是2的幂 */
#define PGLZ_HISTORY_SIZE		4096
#define PGLZ_MAX_MATCH			273


/* ----------
 * PGLZ_HistEntry -
 *
 *		用于向后历史查找的链表
 *
 * 所有共享哈希键的条目都是在双向链表中链接的。
 * 这使得在回收条目时容易删除它
 * （因为它的年龄超过4K位置）。
 * ----------
 */
typedef struct PGLZ_HistEntry
{
	struct PGLZ_HistEntry *next;	/* 我的哈希键列表的链接 */
	struct PGLZ_HistEntry *prev;
	int			hindex;			/* 我当前的哈希键 */
	const char *pos;			/* 我的输入位置 */
} PGLZ_HistEntry;


/* ----------
 * 提供的标准策略
 * ----------
 */
static const PGLZ_Strategy strategy_default_data = {
	32,							/* 小于32字节的数据块不会被
								 * 压缩 */
	INT_MAX,					/* 对我们尝试压缩的内容没有上限 */
	25,							/* 要求25%的压缩率，否则不划算
								 * */
	1024,						/* 如果在前1KB没有压缩，则放弃 */
	128,						/* 如果找到128字节的匹配，则停止历史查找 */
	10							/* 在每次循环迭代中将良好匹配大小降低10% */
};
const PGLZ_Strategy *const PGLZ_strategy_default = &strategy_default_data;


static const PGLZ_Strategy strategy_always_data = {
	0,							/* 任意大小的块都被压缩 */
	INT_MAX,
	0,							/* 只需节省一个字节即可 */
	INT_MAX,					/* 永远不要提前放弃 */
	128,						/* 如果找到128字节的匹配，则停止历史查找 */
	6							/* 更加努力地寻找良好匹配 */
};
const PGLZ_Strategy *const PGLZ_strategy_always = &strategy_always_data;


/* ----------
 * 静态分配的历史工作数组
 * ----------
 */
static int16 hist_start[PGLZ_MAX_HISTORY_LISTS];
static PGLZ_HistEntry hist_entries[PGLZ_HISTORY_SIZE + 1];

/*
 * hist_entries中的元素0未使用，代表“无效”。同样，
 * next/prev指针中的INVALID_ENTRY_PTR也表示“无效”。
 */
#define INVALID_ENTRY			0
#define INVALID_ENTRY_PTR		(&hist_entries[INVALID_ENTRY])

/* ----------
 * pglz_hist_idx -
 *
 *		通过输入的下一个4个字符计算历史表槽位进行查找。
 *
 * 注意：因为我们使用下一个4个字符，所以我们不能保证
 * 找到3个字符的匹配；它们很可能会在错误的
 * 哈希列表中。这似乎是为了更好地分散哈希键而做的可接受的权衡。
 * ----------
 */
#define pglz_hist_idx(_s,_e, _mask) (										\
			((((_e) - (_s)) < 4) ? (int) (_s)[0] :							\
			 (((_s)[0] << 6) ^ ((_s)[1] << 4) ^								\
			  ((_s)[2] << 2) ^ (_s)[3])) & (_mask)				\
		)


/* ----------
 * pglz_hist_add -
 *
 *		将新条目添加到历史表中。
 *
 * 如果_recycle为真，那么我们正在回收一个先前使用的条目，
 * 必须首先将其从其旧哈希码的链表中取消链接。
 *
 * 注意：要小心宏参数的多重评估，并注意
 * _hn和_recycle在宏中被修改。
 * ----------
 */
#define pglz_hist_add(_hs,_he,_hn,_recycle,_s,_e, _mask)	\
do {									\
			int fc___hindex = pglz_hist_idx((_s),(_e), (_mask));				\
			int16 *fc___myhsp = &(_hs)[fc___hindex];								\
			PGLZ_HistEntry *fc___myhe = &(_he)[_hn];							\
			if (_recycle) {													\
				if (fc___myhe->prev == NULL)									\
					(_hs)[fc___myhe->hindex] = fc___myhe->next - (_he);			\
				else														\
					fc___myhe->prev->next = fc___myhe->next;						\
				if (fc___myhe->next != NULL)									\
					fc___myhe->next->prev = fc___myhe->prev;						\
			}																\
			fc___myhe->next = &(_he)[*fc___myhsp];								\
			fc___myhe->prev = NULL;											\
			fc___myhe->hindex = fc___hindex;										\
			fc___myhe->pos  = (_s);											\
			/* 如果在此哈希槽中存在现有条目，则链接 */	\
			/* 此新条目到它。然而，条目表中的第0个条目 */		\
			/* 未使用，因此我们可以自由地在其上写入。 */ \
			/* 所以不要检查该槽是否被使用 - 如果没有使用， */		\
			/* 我们将写在未使用的条目上，但这 */	\
			/* 是无害的。在这个关键路径中避免分支 */		\
			/* 会加快一点速度。 */								\
			/* if (*__myhsp != INVALID_ENTRY) */							\
				(_he)[(*fc___myhsp)].prev = fc___myhe;							\
			*fc___myhsp = _hn;													\
			if (++(_hn) >= PGLZ_HISTORY_SIZE + 1) {							\
				(_hn) = 1;													\
				(_recycle) = true;											\
			}																\
} while (0)


/* ----------
 * pglz_out_ctrl -
 *
 *		输出最后一个，并在需要时分配一个新的控制字节。
 * ----------
 */
#define pglz_out_ctrl(__ctrlp,__ctrlb,__ctrl,__buf) \
do { \
	if ((__ctrl & 0xff) == 0)												\
	{																		\
		*(__ctrlp) = __ctrlb;												\
		__ctrlp = (__buf)++;												\
		__ctrlb = 0;														\
		__ctrl = 1;															\
	}																		\
} while (0)


/* ----------
 * pglz_out_literal -
 *
 *		输出一个字面字节到目标缓冲区，包括
 *		适当的控制位。
 * ----------
 */
#define pglz_out_literal(_ctrlp,_ctrlb,_ctrl,_buf,_byte) \
do { \
	pglz_out_ctrl(_ctrlp,_ctrlb,_ctrl,_buf);								\
	*(_buf)++ = (unsigned char)(_byte);										\
	_ctrl <<= 1;															\
} while (0)


/* ----------
 * pglz_out_tag -
 *
 *		将一个后向引用标记（2-4字节，取决于偏移量和长度）输出到目标缓冲区，包括适当的控制位。
 * ----------
 */
#define pglz_out_tag(_ctrlp,_ctrlb,_ctrl,_buf,_len,_off) \
do { \
	pglz_out_ctrl(_ctrlp,_ctrlb,_ctrl,_buf);								\
	_ctrlb |= _ctrl;														\
	_ctrl <<= 1;															\
	if (_len > 17)															\
	{																		\
		(_buf)[0] = (unsigned char)((((_off) & 0xf00) >> 4) | 0x0f);		\
		(_buf)[1] = (unsigned char)(((_off) & 0xff));						\
		(_buf)[2] = (unsigned char)((_len) - 18);							\
		(_buf) += 3;														\
	} else {																\
		(_buf)[0] = (unsigned char)((((_off) & 0xf00) >> 4) | ((_len) - 3)); \
		(_buf)[1] = (unsigned char)((_off) & 0xff);							\
		(_buf) += 2;														\
	}																		\
} while (0)


/* ----------
 * pglz_find_match -
 *
 *		查找历史表，看看实际输入流是否与输入缓冲区中某个较早位置的其他字符序列匹配。
 * ----------
 */
static inline int fc_pglz_find_match(int16 *fc_hstart, const char *fc_input, const char *fc_end,
				int *fc_lenp, int *fc_offp, int fc_good_match, int fc_good_drop, int fc_mask)
{
	PGLZ_HistEntry *fc_hent;
	int16		fc_hentno;
	int32		fc_len = 0;
	int32		fc_off = 0;

	/*
	 * 遍历链表历史记录，直到找到足够好的匹配。
	 */
	fc_hentno = fc_hstart[pglz_hist_idx(fc_input, fc_end, fc_mask)];
	fc_hent = &hist_entries[fc_hentno];
	while (fc_hent != INVALID_ENTRY_PTR)
	{
		const char *fc_ip = fc_input;
		const char *fc_hp = fc_hent->pos;
		int32		fc_thisoff;
		int32		fc_thislen;

		/*
		 * 如果偏移量不再适合我们的标记，则停止。
		 */
		fc_thisoff = fc_ip - fc_hp;
		if (fc_thisoff >= 0x0fff)
			break;

		/*
		 * 确定匹配的长度。更好的匹配必须大于目前为止的最佳匹配。如果我们已经有了16个字节或更多的匹配，那么使用memcmp()检查匹配的大小是否相等是值得的。在那之后，我们必须回退到逐字符比较，以知道差异发生的确切位置。
		 */
		fc_thislen = 0;
		if (fc_len >= 16)
		{
			if (memcmp(fc_ip, fc_hp, fc_len) == 0)
			{
				fc_thislen = fc_len;
				fc_ip += fc_len;
				fc_hp += fc_len;
				while (fc_ip < fc_end && *fc_ip == *fc_hp && fc_thislen < PGLZ_MAX_MATCH)
				{
					fc_thislen++;
					fc_ip++;
					fc_hp++;
				}
			}
		}
		else
		{
			while (fc_ip < fc_end && *fc_ip == *fc_hp && fc_thislen < PGLZ_MAX_MATCH)
			{
				fc_thislen++;
				fc_ip++;
				fc_hp++;
			}
		}

		/*
		 * 将此匹配记住为最佳（如果是的话）
		 */
		if (fc_thislen > fc_len)
		{
			fc_len = fc_thislen;
			fc_off = fc_thisoff;
		}

		/*
		 * 进位到下一个历史条目
		 */
		fc_hent = fc_hent->next;

		/*
		 * 在访问的条目越多时，对较差的匹配要心满意足。但是，如果我们在列表末尾，则没有必要进行计算。
		 */
		if (fc_hent != INVALID_ENTRY_PTR)
		{
			if (fc_len >= fc_good_match)
				break;
			fc_good_match -= (fc_good_match * fc_good_drop) / 100;
		}
	}

	/*
	 * 仅在至少减少一个字节时返回匹配信息。
	 */
	if (fc_len > 2)
	{
		*fc_lenp = fc_len;
		*fc_offp = fc_off;
		return 1;
	}

	return 0;
}


/* ----------
 * pglz_compress -
 *
 *		使用策略将源压缩到目标中。返回写入缓冲区目标的字节数，如果压缩失败，则返回-1。
 * ----------
 */
int32 pglz_compress(const char *fc_source, int32 fc_slen, char *fc_dest,
			  const PGLZ_Strategy *fc_strategy)
{
	unsigned char *fc_bp = (unsigned char *) fc_dest;
	unsigned char *fc_bstart = fc_bp;
	int			fc_hist_next = 1;
	bool		fc_hist_recycle = false;
	const char *fc_dp = fc_source;
	const char *fc_dend = fc_source + fc_slen;
	unsigned char fc_ctrl_dummy = 0;
	unsigned char *fc_ctrlp = &fc_ctrl_dummy;
	unsigned char fc_ctrlb = 0;
	unsigned char fc_ctrl = 0;
	bool		fc_found_match = false;
	int32		fc_match_len;
	int32		fc_match_off;
	int32		fc_good_match;
	int32		fc_good_drop;
	int32		fc_result_size;
	int32		fc_result_max;
	int32		fc_need_rate;
	int			fc_hashsz;
	int			fc_mask;

	/*
	 * 我们的回退策略是默认的。
	 */
	if (fc_strategy == NULL)
		fc_strategy = PGLZ_strategy_default;

	/*
	 * 如果策略禁止压缩（完全禁止或源块大小超出范围），则失败。
	 */
	if (fc_strategy->match_size_good <= 0 ||
		fc_slen < fc_strategy->min_input_size ||
		fc_slen > fc_strategy->max_input_size)
		return -1;

	/*
	 * 限制匹配参数在支持的范围内。
	 */
	fc_good_match = fc_strategy->match_size_good;
	if (fc_good_match > PGLZ_MAX_MATCH)
		fc_good_match = PGLZ_MAX_MATCH;
	else if (fc_good_match < 17)
		fc_good_match = 17;

	fc_good_drop = fc_strategy->match_size_drop;
	if (fc_good_drop < 0)
		fc_good_drop = 0;
	else if (fc_good_drop > 100)
		fc_good_drop = 100;

	fc_need_rate = fc_strategy->min_comp_rate;
	if (fc_need_rate < 0)
		fc_need_rate = 0;
	else if (fc_need_rate > 99)
		fc_need_rate = 99;

	/*
	 * 计算策略允许的最大结果大小，即输入大小减去最低所需的压缩率。这个值最好小于等于slen，否则我们可能会超出提供的输出缓冲区。
	 */
	if (fc_slen > (INT_MAX / 100))
	{
		/* 近似以避免溢出 */
		fc_result_max = (fc_slen / 100) * (100 - fc_need_rate);
	}
	else
		fc_result_max = (fc_slen * (100 - fc_need_rate)) / 100;

	/*
	 * 实验表明，这些哈希大小效果很好。大的哈希表可以最小化碰撞，但启动成本较高。对于小输入，启动成本占主导地位。表大小必须是2的幂。
	 */
	if (fc_slen < 128)
		fc_hashsz = 512;
	else if (fc_slen < 256)
		fc_hashsz = 1024;
	else if (fc_slen < 512)
		fc_hashsz = 2048;
	else if (fc_slen < 1024)
		fc_hashsz = 4096;
	else
		fc_hashsz = 8192;
	fc_mask = fc_hashsz - 1;

	/*
	 * 将历史列表初始化为空。我们不需要将hist_entries[]数组归零；其条目在使用时被初始化。
	 */
	memset(hist_start, 0, fc_hashsz * sizeof(int16));

	/*
	 * 直接将源压缩到输出缓冲区。
	 */
	while (fc_dp < fc_dend)
	{
		/*
		 * 如果我们已经超过了最大结果大小，则失败。
		 *
		 * 我们每次循环检查一次；由于循环体可能会产生多达4个字节（一个控制字节和3字节标记），PGLZ_MAX_OUTPUT()最好能允许4个边际字节。
		 */
		if (fc_bp - fc_bstart >= fc_result_max)
			return -1;

		/*
		 * 如果我们在没有找到任何可压缩内容的情况下已经发出了超过first_success_by字节的内容，则失败。这让我们在查看不可压缩输入（例如预压缩数据）时能够合理迅速地退出。
		 */
		if (!fc_found_match && fc_bp - fc_bstart >= fc_strategy->first_success_by)
			return -1;

		/*
		 * 尝试在历史记录中找到匹配
		 */
		if (fc_pglz_find_match(hist_start, fc_dp, fc_dend, &fc_match_len,
							&fc_match_off, fc_good_match, fc_good_drop, fc_mask))
		{
			/*
			 * 创建标签并为所有匹配的字符添加历史条目。
			 */
			pglz_out_tag(fc_ctrlp, fc_ctrlb, fc_ctrl, fc_bp, fc_match_len, fc_match_off);
			while (fc_match_len--)
			{
				pglz_hist_add(hist_start, hist_entries,
							  fc_hist_next, fc_hist_recycle,
							  fc_dp, fc_dend, fc_mask);
				fc_dp++;			/* 不要在上面的行中做这个++！ */
				/* 宏会执行四次 - 一月。 */
			}
			fc_found_match = true;
		}
		else
		{
			/*
			 * 没有找到匹配。复制一个文字字节。
			 */
			pglz_out_literal(fc_ctrlp, fc_ctrlb, fc_ctrl, fc_bp, *fc_dp);
			pglz_hist_add(hist_start, hist_entries,
						  fc_hist_next, fc_hist_recycle,
						  fc_dp, fc_dend, fc_mask);
			fc_dp++;				/* 不要在上面的行中做这个++！ */
			/* 宏会执行四次 - 一月。 */
		}
	}

	/*
	 * 写出最后一个控制字节，并检查是否没有超过策略允许的
	 * 输出大小。
	 */
	*fc_ctrlp = fc_ctrlb;
	fc_result_size = fc_bp - fc_bstart;
	if (fc_result_size >= fc_result_max)
		return -1;

	/* 成功 */
	return fc_result_size;
}


/* ----------
 * pglz_decompress -
 *
 *		将源解压到目标。返回解压到目标缓冲区的字节数，
 *		如果压缩数据已损坏则返回-1。
 *
 *		如果check_complete为真，则如果我们没有
 *		完全填满目标缓冲区，则数据被视为损坏。
 *		提取切片的调用者通常无法应用此检查。
 * ----------
 */
int32 pglz_decompress(const char *fc_source, int32 fc_slen, char *fc_dest,
				int32 fc_rawsize, bool fc_check_complete)
{
	const unsigned char *fc_sp;
	const unsigned char *fc_srcend;
	unsigned char *fc_dp;
	unsigned char *fc_destend;

	fc_sp = (const unsigned char *) fc_source;
	fc_srcend = ((const unsigned char *) fc_source) + fc_slen;
	fc_dp = (unsigned char *) fc_dest;
	fc_destend = fc_dp + fc_rawsize;

	while (fc_sp < fc_srcend && fc_dp < fc_destend)
	{
		/*
		 * 读取一个控制字节并处理接下来的8个项（或压缩输入中剩余的项目）。
		 */
		unsigned char fc_ctrl = *fc_sp++;
		int			fc_ctrlc;

		for (fc_ctrlc = 0; fc_ctrlc < 8 && fc_sp < fc_srcend && fc_dp < fc_destend; fc_ctrlc++)
		{
			if (fc_ctrl & 1)
			{
				/*
				 * 设置控制位意味着我们必须读取一个匹配标签。匹配
				 * 用两个字节编码。第一个字节使用低半字节来
				 * 编码长度 - 3。高半字节包含偏移的高4位。
				 * 下一个字节包含偏移的低8位。如果长度编码为18，另一个
				 * 扩展标签字节指示匹配实际上有多长（0-255）。
				 */
				int32		fc_len;
				int32		fc_off;

				fc_len = (fc_sp[0] & 0x0f) + 3;
				fc_off = ((fc_sp[0] & 0xf0) << 4) | fc_sp[1];
				fc_sp += 2;
				if (fc_len == 18)
					fc_len += *fc_sp++;

				/*
				 * 检查损坏的数据：如果我们超出了源的末尾，
				 * 或者如果我们获得off = 0，或者如果off超过
				 * 缓冲区开始的回退距离，我们就有问题。
				 * （我们必须检查off = 0，否则在面对损坏数据时
				 * 风险无穷循环。 同样，off的上限防止访问缓冲区
				 * 边界之外。）
				 */
				if (unlikely(fc_sp > fc_srcend || fc_off == 0 ||
							 fc_off > (fc_dp - (unsigned char *) fc_dest)))
					return -1;

				/*
				 * 不要输出超过请求的数据。
				 */
				fc_len = Min(fc_len, fc_destend - fc_dp);

				/*
				 * 现在我们从OUTPUT复制标签指定的字节到
				 * OUTPUT（从dp - off复制len字节到dp）。复制的
				 * 区域可能重叠，因此为了避免memcpy()中的未定义行为，
				 * 要小心只复制非重叠区域。
				 *
				 * 请注意，我们不能使用memmove()，因为尽管它的
				 * 行为是明确的，但它也不是我们想要的。
				 */
				while (fc_off < fc_len)
				{
					/*
					 * 我们可以安全地复制“off”字节，因为这明确
					 * 结果为源和目标不重叠。
					 */
					memcpy(fc_dp, fc_dp - fc_off, fc_off);
					fc_len -= fc_off;
					fc_dp += fc_off;

					/*----------
					 * 这个部分不太明显：我们可以在每一步后将“off”加倍。
					 * 考虑这个原始输入：
					 *		112341234123412341234
					 * 这将被编码为 5 个字面字节“11234”，然后是一个长度为 16 和偏移量为 4 的匹配标签。
					 * 在 memcpy 前 4 个字节之后，我们将发出：
					 *		112341234
					 * 所以我们可以将“off”加倍到 8，然后在下一步之后我们发出：
					 *		11234123412341234
					 * 然后我们可以再次将“off”加倍，此后它超过剩余的“len”，所以我们跳出这个循环
					 * 并用剩余部分的非重叠副本结束。一般来说，偏移量小于长度的匹配标签
					 * 表明解码数据的重复长度为“off”。我们可以处理 1、2、4 等重复直到
					 * 我们达到最终复制步骤是非重叠的情况。
					 *
					 * （另一种理解这个的方式是，我们保持
					 * 复制源点 dp - off 在整个过程中相同。）
					 *----------
					 */
					fc_off += fc_off;
				}
				memcpy(fc_dp, fc_dp - fc_off, fc_len);
				fc_dp += fc_len;
			}
			else
			{
				/*
				 * 一个未设置的控制位意味着字面字节。因此我们只需将
				 * 一个从输入复制到输出。
				 */
				*fc_dp++ = *fc_sp++;
			}

			/*
			 * 前进控制位
			 */
			fc_ctrl >>= 1;
		}
	}

	/*
	 * 如果要求，检查我们解压缩的量是否正确。
	 */
	if (fc_check_complete && (fc_dp != fc_destend || fc_sp != fc_srcend))
		return -1;

	/*
	 * 就这样。
	 */
	return (char *) fc_dp - fc_dest;
}


/* ----------
 * pglz_maximum_compressed_size -
 *
 *		计算给定数量原始数据的最大压缩大小。
 *		返回最大大小，或者如果最大大小大于总压缩大小，则返回总压缩大小。
 *
 * 我们不能为此目的使用 PGLZ_MAX_OUTPUT，因为它用于设置
 * 压缩缓冲区的大小（并中止压缩）。它并没有真正说明
 * 在给定长度的输入的最大压缩大小是什么，而且可能发生的情况是
 * 虽然整个值是可压缩的（因此很好地适合 PGLZ_MAX_OUTPUT），
 * 但前缀并不可压缩。
 * ----------
 */
int32 pglz_maximum_compressed_size(int32 fc_rawsize, int32 fc_total_compressed_size)
{
	int64		fc_compressed_size;

	/*
	 * pglz 每个字节使用一个控制位，因此如果整个所需前缀
	 * 被表示为字面字节，我们将需要（rawsize * 9）位。
	 * 但是我们关心的是字节，所以一定要向上取整而不是向下取整。
	 *
	 * 此处使用 int64 以防止在计算过程中溢出。
	 */
	fc_compressed_size = ((int64) fc_rawsize * 9 + 7) / 8;

	/*
	 * 上述未考虑一个特例：我们可能有压缩
	 * 的数据以 N-1 或 N-2 字面字节开头，然后有一个 2 或 3 字节的匹配标签。
	 * 因此，我们可能需要获取 1 或 2 个字节，以便拥有整个匹配标签。
	 * （压缩数据早期的匹配标签不会造成问题，因为它们的表示
	 * 的解压缩字节应该比它们自己占用的字节多。）
	 */
	fc_compressed_size += 2;

	/*
	 * 最大压缩大小不能大于总压缩大小。
	 * （这也确保我们的结果适合 int32。）
	 */
	fc_compressed_size = Min(fc_compressed_size, fc_total_compressed_size);

	return (int32) fc_compressed_size;
}
